package leetcode;

import java.util.Arrays;
import java.util.PriorityQueue;

public class LC1631 {

    public static int minimumEffortPath(int[][] heights) {
        int n = heights.length;
        int m = heights[0].length;
        boolean[][] visited = new boolean[n][m];
        int[][] dist = new int[n][m];
        for (int i = 0; i < dist.length; i++) {
            Arrays.fill(dist[i],Integer.MAX_VALUE);
        }
        int[] dx = {0,0,-1,1};
        int[] dy = {-1,1,0,0};
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[2] - b[2]));
        pq.offer(new int[]{0, 0, 0});
        dist[0][0] = 0;
        while (!pq.isEmpty()) {
            int[] node = pq.poll();
            int x = node[0];
            int y = node[1];
            int effort = node[2];
            if (visited[x][y]) continue;
            if (x == n - 1 && y == m -1) break;
            visited[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < n && ny < m && nx >= 0 && ny >= 0 &&
                    dist[nx][ny] > Math.max(effort,Math.abs(heights[x][y] - heights[nx][ny]))) {
                    dist[nx][ny] = Math.max(effort,Math.abs(heights[x][y] - heights[nx][ny]));
                    pq.offer(new int[]{nx,ny,dist[nx][ny]});
                }
            }
        }
        return dist[n - 1][m - 1];
    }

    public static void main(String[] args) {
        int heights[][] = {{1,2,3},{3,8,4},{5,3,5}};
        minimumEffortPath(heights);
    }
}
